Given a preference game over player set $[n] = \{1, \ldots, n\}$, with the sum of the lengths of the preference lists equal to $m$. Assume that each player exists in the preference list (ahead of ``self'') for at most $m'$ other players.

\subsubsection*{Reducing to a preference game with constant out-degree (at most $c+1$), with $O(m+n)$ players.}

Suppose player $i$ in the original game has preference list $j_1, j_2, \ldots, j_k$.  Let $d = \lceil \frac{k}{c} \rceil$. Create $2d$ new players, split into two sets: $I = \{i_1, \ldots, i_d\}, I' = \{i'_1, \ldots, i'_d\}$. For ease of notation, we will also refer to player $i_d$ as $i^*$, since this is the player that will play itself the same amount that the original player $i$ should play itself. 

Set the preference list for the new player $i_1$ to $j_1^*, j_2^*, \ldots j_c^*, i_1$. For new player $i_h$ ($h > 1$), set the preference list to $i'_{h-1}, j_{(h-1)c + 1}^*, j_{(h-1)c + 2}^*, \ldots, j_{hc}^*, i_h$. For each new player $i'_h$ ($h \geq 1$), set the preference list to $i_h, i'_h$.

\subsubsection*{Equilibrium in the original preference game maps to an equilibrium in the new preference game.}
The map will be as follows: Suppose we are given weights $w(i,j)$ for the original game, where $w(i,j)$ is the weight player $i$ puts on player $j$. We will set the weights $w^*$ in the new preference game as follows. Again, assume the preference list for player $i$ in the original game is $j_1, j_2, \ldots, j_k$.
\begin{itemize}
\item $w^*(i_h, j^*) = w(i,j)$ for all $j^*$ in the preference list of $i_h$.
\item $w^*(i_h, i'_{h-1}) = \sum_{l=1}^{(h-1)c} w(i,j_l)$
\item $w^*(i_h, i_h) = 1 - \sum_{l=1}^{hc} w(i, j_l)$
\item $w^*(i'_h, i_h) = 1 - \sum_{l=1}^{hc} w(i, j_l)$
\item $w^*(i'_h, i'_h) = \sum_{l=1}^{hc} w(i, j_l)$
\end{itemize}

Notice, 
\begin{alignat*}{2}
w^*(i^*, i^*) & = w^*(i_d, i_d) && \textrm{ (by definition of $i^*$)} \\
& = 1 - \sum_{l=1}^{dc} w(i, j_l) && \textrm{ (from map above)} \\
& = 1 - \sum_{l=1}^{\lceil \frac{k}{c} \rceil c} w(i, j_l)  && \textrm{ (by definition of $d$) } \\
& = 1 - \sum_{l=1}^{k} w(i, j_l) && \textrm{ (we can ignore the $\lceil \rceil$ since the} \\
& && \textrm{  preference list stops after $k$ items) }\\
& = w(i,i) &&
\end{alignat*}

In order to verify that this is an equilibrium in the new game, we must check the following
\begin{enumerate}
\item $w^*(i,j) \leq w^*(j,j)$ for all $i, j$. \label{feasible}
\item $w^*(i,i) + \sum_{j \neq i} w^*(i,j) = 1$ for all $i$. \label{sumToOne}
\item If $w^*(i,j) > 0$, and if $i$ prefers $a$ over $j$, then $w^*(i,a) = w^*(a, a)$. \label{optimal}
\end{enumerate}

All three of these are trivial for players in $I'$, so we will verify the conditions for players in $I$. First consider condition \ref{feasible} for each weight placed by a player in set $I$. 
\begin{itemize}
\item $w^*(i_h, a^*) = 0$ unless $a^*$ is in the preference list for $i_h$. If $a^*$ is in the preference list, then $a^* = a'_p$ for some player $a$ from the original game with $p = \lceil$ length of $a$'s preference list $/ c \rceil$, and $w^*(a^*, a^*) = w(a,a)$. By the map above, $w^*(i_h, a^*) = w(i,a)$. Since $w(i,a) \leq w(a,a)$, $w^*(i_h, a^*)$ obeys condition \ref{feasible}.
\item $w^*(i_h, i'_{h-1}) = \sum_{l=1}^{(h-1)c} w(i,j_l)$. But we know from the map that $$w^*(i'_{h-1}, i'_{h-1}) = \sum_{l=1}^{(h-1)c} w(i, j_l)$$ so $w^*(i_h, i'_{h-1})$ also obeys condition \ref{feasible}.
\end{itemize}

Next, check condition \ref{sumToOne} for each player in set $I$. The total weight placed by player $i_h$ is 
\begin{eqnarray*}
&& w^*(i_h, i_h) + w^*(i_h, i'_{h-1}) + \sum_{j^* \textrm{ in the pref list of } i_h} w^*(i_h, j^*)   \\
&=& 1 - \sum_{l=1}^{hc} w(i, j_l) + \sum_{l=1}^{(h-1)c} w(i,j_l) + \sum_{j^* \textrm{ in the pref list of } i_h} w(i,j) \\
&=& 1 - \sum_{l=(h-1)c + 1}^{hc} w(i, j_l) + \sum_{l=(h-1)c + 1}^{hc} w(i,j_l) \\
&=& 1
\end{eqnarray*}

Finally, check condition \ref{optimal}. From above, we know that $w^*(i_h, i'_{h-1}) = w^*(i'_{h-1}, i'_{h-1})$, so the first element in each preference list in the new game (the first preference of $i_h$ is for $i'_{h-1}$) will always obey $w^*(i,a) = w^*(a, a)$.  Also from above, $w^*(j^*, j^*) = w(j,j)$ and $w^*(i_h, j^*) = w(i,j)$. Therefore, if any lower preference disobeys $w^*(i,a) = w^*(a, a)$, then it must also be true that $w(i,a) \neq w(a,a)$. Since we assumed the $w$ values were an equilibrium in the original game, this must mean that there is no $b$ preferred less than $a$ with $w(i,b) > 0$, so for all $b^*$ preferred less than $a^*$, $w^*(i_h, b^*) = 0$. 

\subsubsection*{Equilibrium in the new preference game maps to an equilibrium in the original preference game.}
This map is simple. Given weights $w^*$ in the new preference game, create weights $w$ in the original preference game as follows.
\begin{itemize}
\item $w(i,j) = \max_{h} w^*(i_h, j^*)$
\item $w(i,i) = w^*(i^*, i^*)$
\end{itemize}
The $\max$ in the first rule is a notational shortcut, since only one of the $i_h$ players will have any preference for $j^*$, and therefore at most one of the $i_h$ players will have $w^*(i_h, j^*) > 0$.

As before, we need to show the following to verify that this is an equilibrium in the original game.
\begin{enumerate}
\item $w(i,j) \leq w(j,j)$ for all $i, j$. 
\item $w(i,i) + \sum_{j \neq i} w(i,j) = 1$ for all $i$. 
\item If $w(i,j) > 0$, and if $i$ prefers $a$ over $j$, then $w(i,a) = w(a, a)$. 
\end{enumerate}

To show condition \ref{feasible}, consider players $i$ and $j$. Let $i_h$ = the player in the new game that has $j^*$ in its preference list. Now, $w(i,j) = w^*(i_h, j^*)$ and $w(j,j) = w^*(j^*, j^*)$. Since $w^*$ was feasible, we know that $w^*(i_j, j^*) \leq w^*(j^*, j^*)$, as desired.

Next, to show condition \ref{sumToOne}, consider player $i$. $w(i,i) + \sum_{x=1}^k w(i,j_x)$ $=$ $w^*(i^*, i^*) + \sum_{x=1}^k \max_h w^*(i_h, j_x^*)$.  Let's compute $w^*(i^*, i^*)$ in the new preference game. Recall, the preference list for player $i_h$ is $i'_{h-1}$, $j_{(h-1)c + 1}^*$, $j_{(h-1)c + 2}^*$, $\ldots$, $j_{hc}^*$, $i_h$, and specifically, the preference list for $i^*$ ($= i_d$) is $i'_{d-1}$, $j_{(d-1)c + 1}^*$, $j_{(d-1)c + 2}^*$, $\ldots$, $j_{k}^*$, $i_d$. Thus, 
\allowdisplaybreaks{
\begin{eqnarray*}
w^*(i^*, i^*) &=& 1 - w^*(i_d, i'_{d-1}) - \sum_{x=(d-1)c + 1}^{k} w^*(i_d, j_x^*) \\
& = & 1 - w^*(i'_{d-1}, i'_{d-1}) - \sum_{x=(d-1)c + 1}^{k} \max_h w^*(i_h, j_x^*) \\
& = & 1 - \left( 1 - w^*(i'_{d-1}, i_{d-1}) \right) - \sum_{x=(d-1)c + 1}^{k} \max_h w^*(i_h, j_x^*) \\
& = & w^*(i'_{d-1}, i_{d-1}) - \sum_{x=(d-1)c + 1}^{k} \max_h w^*(i_h, j_x^*) \\
& = & w^*(i_{d-1}, i_{d-1}) - \sum_{x=(d-1)c + 1}^{k} \max_h w^*(i_h, j_x^*) \\
& = & 1 - \left( w^*(i_{d-1}, i'_{d-2}) + \sum_{x=(d-2)c + 1}^{(d-1)c} w^*(i_{d-1}, j_x^*) \right) \\
&& - \sum_{x=(d-1)c + 1}^{k} \max_h w^*(i_h, j_x^*) \\
& = & 1 - w^*(i'_{d-2}, i'_{d-2}) - \sum_{x=(d-2)c + 1}^{(d-1)c} \max_h w^*(i_h, j_x^*) \\
&& - \sum_{x=(d-1)c + 1}^{k} \max_h w^*(i_h, j_x^*) \\
& = & 1 - w^*(i'_{d-2}, i'_{d-2}) - \sum_{x=(d-2)c + 1}^{dc} \max_h w^*(i_h, j_x^*) \\
& = & \ldots \\
& = & 1 - w^*(i'_1, i'_1) - \sum_{x=c + 1}^{k} \max_h w^*(i_h, j_x^*) \\
& = & 1 - \left( 1 - w^*(i'_1, i_1) \right) - \sum_{x=c + 1}^{k} \max_h w^*(i_h, j_x^*) \\
& = & w^*(i_1, i_1) - \sum_{x=c + 1}^{k} \max_h w^*(i_h, j_x^*) \\
& = & 1 - \sum_{x=1}^{c} w^*(i_1, j_x^*) - \sum_{x=c + 1}^{k} \max_h w^*(i_h, j_x^*) \\
& = & 1 - \sum_{x=1}^{c} \max_h w^*(i_h, j_x^*) - \sum_{x=c + 1}^{k} \max_h w^*(i_h, j_x^*) \\
& = & 1 - \sum_{x=1}^{k} \max_h w^*(i_h, j_x^*) \\
\end{eqnarray*}
}

Putting this back into our sum for player $i$, we get 
\begin{eqnarray*}
w(i,i) + \sum_{x=1}^k w(i,j_x) & = & w^*(i^*, i^*) + \sum_{x=1}^k \max_h w^*(i_h, j_x^*) \\
& =  & 1 - \sum_{x=1}^{k} \max_h w^*(i_h, j_x^*) + \sum_{x=1}^k \max_h w^*(i_h, j_x^*) = 1. 
\end{eqnarray*}
So \ref{sumToOne} holds.

Finally, we need to verify if $w(i,j) > 0$, and if $i$ prefers $a$ over $j$, then $w(i,a) = w(a, a)$. If $w(i,j) > 0$, then $\max_{h} w^*(i_h, j^*) > 0$. Let $h$ = the $h$ that satisfies $\max_h w^*(i_h, j^*)$. Now, if $i$ prefers $a$ over $j$, then either (Case 1) $i_h$ prefers $a^*$ over $j^*$ or (Case 2) there is some $b < h$ such that $i_b$ has preference for $a^*$. Start with Case 1. Since we know that $w^*$ is an equilibrium for the new preference game, it must be true that $w^*(i_h, a^*) = w^*(a^*, a^*)$, so $w(i,a) = w(a,a)$, as desired. 

For Case 2, since $w^*(i_h, j^*) > 0$, we know that for all $b<h$, $w^*(i'_b, i'_b) < 1$ (otherwise, for all $c > b$, $i_c$ would put weight 1 on $i'_{c-1}$, leaving no weight left for itself, so $i'_c$ would also be 1. Therefore, $i_h$ would put weight 1 on $i_{h-1}$, leaving no weight for $j^*$.) Therefore, for the $b$ with preference for $a^*$, $w^*(i'_b, i'_b) < 1 \Rightarrow w^*(i'_b, i_b) > 0 \Rightarrow w^*(i_b, i_b) > 0$. Therefore, for all $c^*$ in the preference list for $i_b$ (including $a^*$), $w^*(i_b, c^*) = w^*(c^*, c^*)$. So $w^*(i_b, a^*) = w^*(a^*, a^*)$, so $w(i,a) = w^*(i_b, a^*) = w^*(a^*, a^*) = w(a,a)$, as desired.

\subsubsection*{Reducing to a preference game with constant in-degree (at most 2), with $O(m'n)$ players.}

Suppose we have a player $i$ who exists in the preference lists of $m'$ other players: $j_1, j_2, \ldots, j_{m'}$. We will add extra players $i'_1, i_1, i'_2, i_2, \ldots, i'_{m'}, i_{m'}$. The preference lists for these new players will be: $i'_1$ has list $(i, i'_1)$, for all $k>1$: $i'_k$ has list $(i_{k-1}, i'_k)$, for all $k$, $i_k$ has list $(i'_k, i_k)$. If $i$ plays itself with weight $v$, then $i'_k$ will play itself with weight $1 - v$ and $i_k$ will play itself with weight $v$. Each of these new players has in-degree 1 and out-degree 1. Now, we can replace $i$ with $i_k$ in the preference list for $j_k$, so that $i$ now has in-degree 1 and each $i_k$ has in-degree 2. This does not affect the degree of any $j_k$.